/*-------------------------------------------------------------------------
 *
 * ginbulk.c
 *	  用于快速构建倒排索引的例程
 *
 *
 * Portions Copyright (c) 1996-2022, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 * IDENTIFICATION
 *			src/backend/access/gin/ginbulk.c
 *-------------------------------------------------------------------------
 */

#include "postgres.h"

#include <limits.h>

#include "access/gin_private.h"
#include "utils/datum.h"
#include "utils/memutils.h"


#define DEF_NENTRY	2048		/* GinEntryAccumulator allocation quantum */
#define DEF_NPTR	5			/* ItemPointer initial allocation quantum */


/* Combiner function for rbtree.c */
static void fc_ginCombineData(RBTNode *fc_existing, const RBTNode *fc_newdata, void *fc_arg)
{
	GinEntryAccumulator *fc_eo = (GinEntryAccumulator *) fc_existing;
	const GinEntryAccumulator *fc_en = (const GinEntryAccumulator *) fc_newdata;
	BuildAccumulator *fc_accum = (BuildAccumulator *) fc_arg;

	/*
	 * 请注意，代码假设 newdata 只包含一个 itempointer。
	 */
	if (fc_eo->count >= fc_eo->maxcount)
	{
		if (fc_eo->maxcount > INT_MAX)
			ereport(ERROR,
					(errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
					 errmsg("posting list is too long"),
					 errhint("Reduce maintenance_work_mem.")));

		fc_accum->allocatedMemory -= GetMemoryChunkSpace(fc_eo->list);
		fc_eo->maxcount *= 2;
		fc_eo->list = (ItemPointerData *)
			repalloc_huge(fc_eo->list, sizeof(ItemPointerData) * fc_eo->maxcount);
		fc_accum->allocatedMemory += GetMemoryChunkSpace(fc_eo->list);
	}

	/* 如果 item pointers 没有排序，它们需要稍后进行排序 */
	if (fc_eo->shouldSort == false)
	{
		int			fc_res;

		fc_res = ginCompareItemPointers(fc_eo->list + fc_eo->count - 1, fc_en->list);
		Assert(fc_res != 0);

		if (fc_res > 0)
			fc_eo->shouldSort = true;
	}

	fc_eo->list[fc_eo->count] = fc_en->list[0];
	fc_eo->count++;
}

/* Comparator function for rbtree.c */
static int fc_cmpEntryAccumulator(const RBTNode *fc_a, const RBTNode *fc_b, void *fc_arg)
{
	const GinEntryAccumulator *fc_ea = (const GinEntryAccumulator *) fc_a;
	const GinEntryAccumulator *fc_eb = (const GinEntryAccumulator *) fc_b;
	BuildAccumulator *fc_accum = (BuildAccumulator *) fc_arg;

	return ginCompareAttEntries(fc_accum->ginstate,
								fc_ea->attnum, fc_ea->key, fc_ea->category,
								fc_eb->attnum, fc_eb->key, fc_eb->category);
}

/* Allocator function for rbtree.c */
static RBTNode * fc_ginAllocEntryAccumulator(void *fc_arg)
{
	BuildAccumulator *fc_accum = (BuildAccumulator *) fc_arg;
	GinEntryAccumulator *fc_ea;

	/*
	 * 通过相当大的块分配内存以减少开销。我们无需单独回收 RBTNodes，所以这没有成本。
	 */
	if (fc_accum->entryallocator == NULL || fc_accum->eas_used >= DEF_NENTRY)
	{
		fc_accum->entryallocator = palloc(sizeof(GinEntryAccumulator) * DEF_NENTRY);
		fc_accum->allocatedMemory += GetMemoryChunkSpace(fc_accum->entryallocator);
		fc_accum->eas_used = 0;
	}

	/* 从当前块分配新的 RBTNode */
	fc_ea = fc_accum->entryallocator + fc_accum->eas_used;
	fc_accum->eas_used++;

	return (RBTNode *) fc_ea;
}

void ginInitBA(BuildAccumulator *fc_accum)
{
	/* accum->ginstate 在这里故意不设置 */
	fc_accum->allocatedMemory = 0;
	fc_accum->entryallocator = NULL;
	fc_accum->eas_used = 0;
	fc_accum->tree = rbt_create(sizeof(GinEntryAccumulator),
							 fc_cmpEntryAccumulator,
							 fc_ginCombineData,
							 fc_ginAllocEntryAccumulator,
							 NULL,	/* 不需要 freefunc */
							 (void *) fc_accum);
}

/*
 * 这基本上与 datumCopy() 相同，但扩展为在 accum->allocatedMemory 中计算 palloc 的空间。
 */
static Datum fc_getDatumCopy(BuildAccumulator *fc_accum, OffsetNumber fc_attnum, Datum fc_value)
{
	Form_pg_attribute fc_att;
	Datum		fc_res;

	fc_att = TupleDescAttr(fc_accum->ginstate->origTupdesc, fc_attnum - 1);
	if (fc_att->attbyval)
		fc_res = fc_value;
	else
	{
		fc_res = datumCopy(fc_value, false, fc_att->attlen);
		fc_accum->allocatedMemory += GetMemoryChunkSpace(DatumGetPointer(fc_res));
	}
	return fc_res;
}

/*
 * 从索引值中查找/存储一个条目。
 */
static void fc_ginInsertBAEntry(BuildAccumulator *fc_accum,
				 ItemPointer fc_heapptr, OffsetNumber fc_attnum,
				 Datum fc_key, GinNullCategory fc_category)
{
	GinEntryAccumulator fc_eatmp;
	GinEntryAccumulator *fc_ea;
	bool		fc_isNew;

	/*
	 * 目前，仅填写 eatmp 中将被 cmpEntryAccumulator 或 ginCombineData 查看字段。
	 */
	fc_eatmp.attnum = fc_attnum;
	fc_eatmp.key = fc_key;
	fc_eatmp.category = fc_category;
	/* 临时设置单条目 itempointer 列表 */
	fc_eatmp.list = fc_heapptr;

	fc_ea = (GinEntryAccumulator *) rbt_insert(fc_accum->tree, (RBTNode *) &fc_eatmp,
											&fc_isNew);

	if (fc_isNew)
	{
		/*
		 * 完成初始化新树条目，包括对 datum（如果不为 null）和 itempointer 的永久复制。
		 */
		if (fc_category == GIN_CAT_NORM_KEY)
			fc_ea->key = fc_getDatumCopy(fc_accum, fc_attnum, fc_key);
		fc_ea->maxcount = DEF_NPTR;
		fc_ea->count = 1;
		fc_ea->shouldSort = false;
		fc_ea->list =
			(ItemPointerData *) palloc(sizeof(ItemPointerData) * DEF_NPTR);
		fc_ea->list[0] = *fc_heapptr;
		fc_accum->allocatedMemory += GetMemoryChunkSpace(fc_ea->list);
	}
	else
	{
		/*
		 * ginCombineData 已完成所有必要的操作。
		 */
	}
}

/*
 * 为一个堆指针插入条目。
 *
 * 由于条目被插入到一个平衡的二叉树中，你可能会认为插入的顺序并不重要，但事实证明，以排序顺序插入条目会导致大量的重平衡操作，且速度较慢。为此，我们尝试以一种将生成近乎平衡树的顺序插入节点，假如输入实际上是有序的。
 *
 * 我们的方法如下。首先，我们假设有一个数组，其大小是大于或等于实际数组大小的最小二次幂。第二，我们将虚拟数组的中间条目插入树中；然后，我们插入虚拟数组每一半的中间条目，接着插入四分之一的中间条目，依此类推。
 */
void ginInsertBAEntries(BuildAccumulator *fc_accum,
				   ItemPointer fc_heapptr, OffsetNumber fc_attnum,
				   Datum *fc_entries, GinNullCategory *fc_categories,
				   int32 fc_nentries)
{
	uint32		fc_step = fc_nentries;

	if (fc_nentries <= 0)
		return;

	Assert(ItemPointerIsValid(fc_heapptr) && fc_attnum >= FirstOffsetNumber);

	/*
	 * step 将包含最大次幂 2 且 <= nentries
	 */
	fc_step |= (fc_step >> 1);
	fc_step |= (fc_step >> 2);
	fc_step |= (fc_step >> 4);
	fc_step |= (fc_step >> 8);
	fc_step |= (fc_step >> 16);
	fc_step >>= 1;
	fc_step++;

	while (fc_step > 0)
	{
		int			fc_i;

		for (fc_i = fc_step - 1; fc_i < fc_nentries && fc_i >= 0; fc_i += fc_step << 1 /* *2 */ )
			fc_ginInsertBAEntry(fc_accum, fc_heapptr, fc_attnum,
							 fc_entries[fc_i], fc_categories[fc_i]);

		fc_step >>= 1;				/* /2 */
	}
}

static int fc_qsortCompareItemPointers(const void *fc_a, const void *fc_b)
{
	int			fc_res = ginCompareItemPointers((ItemPointer) fc_a, (ItemPointer) fc_b);

	/* 断言没有相等的 item pointers 被排序 */
	Assert(fc_res != 0);
	return fc_res;
}

/* 准备使用 ginGetBAEntry 读取 rbtree 内容 */
void ginBeginBAScan(BuildAccumulator *fc_accum)
{
	rbt_begin_iterate(fc_accum->tree, LeftRightWalk, &fc_accum->tree_walk);
}

/*
 * 从 BuildAccumulator 的 rbtree 中获取下一个条目。
 * 这由一个单一的键 datum 和一个包含一个或多个堆 TID 的列表（数组）组成，这些堆 TID 中包含该键。该列表保证是排序的。
 */
ItemPointerData *
ginGetBAEntry(BuildAccumulator *fc_accum,
			  OffsetNumber *fc_attnum, Datum *fc_key, GinNullCategory *fc_category,
			  uint32 *fc_n)
{
	GinEntryAccumulator *fc_entry;
	ItemPointerData *fc_list;

	fc_entry = (GinEntryAccumulator *) rbt_iterate(&fc_accum->tree_walk);

	if (fc_entry == NULL)
		return NULL;			/* 没有更多条目 */

	*fc_attnum = fc_entry->attnum;
	*fc_key = fc_entry->key;
	*fc_category = fc_entry->category;
	fc_list = fc_entry->list;
	*fc_n = fc_entry->count;

	Assert(fc_list != NULL && fc_entry->count > 0);

	if (fc_entry->shouldSort && fc_entry->count > 1)
		qsort(fc_list, fc_entry->count, sizeof(ItemPointerData),
			  fc_qsortCompareItemPointers);

	return fc_list;
}
